package written_examination_questions;

import java.util.ArrayList;
import java.util.List;

public class Demo20251111 {
    /**
     * 全排列2
     */
    List<List<Integer>> ret;
    List<Integer> path; // 记录路径
    boolean[] check; // 检查该位置的值是否已经记录过

    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];

        dfs(nums);
        return ret;
    }

    public void dfs(int[] nums) {
        // 递归出口
        if (nums.length == path.size()) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (check[i] == false) { // 未出现过
                path.add(nums[i]);
                check[i] = true;
                // 递归
                dfs(nums);
                // 回溯 将最后一位标记为未出现过
                check[i] = false;
                // 从 path 中移除
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 盛水最多的容器
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        // 双指针
        int left = 0, right = height.length - 1, max = 0;
        while (left < right) {
            int V = Math.min(height[left], height[right]) * (right - left);
            max = Math.max(max, V);
            // 移动指针，移动矮的
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }
}

/*
// 全排列 1
 class Solution {
    List<List<Integer>> ret;
    List<Integer> path; // 记录路径
    boolean[] check; // 检查该位置的值是否已经记录过

    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];

        dfs(nums);
        return ret;
    }

    public void dfs(int[] nums) {
        // 递归出口
        if (nums.length == path.size()) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (check[i] == false) { // 未出现过
                path.add(nums[i]);
                check[i] = true;
                // 递归
                dfs(nums);
                // 回溯 将最后一位标记为未出现过
                check[i] = false;
                // 从 path 中移除
                path.remove(path.size() - 1);
            }
        }
    }
}
 */
